package org.regotto.basics.monotonous;

/**
 * 单调队列, 队列中维持单调性
 */
public class MonotonousQueue {

    public static void main(String[] args) {
        first(new int[]{2, 3, 4, 5, 7, 1, 0}, 3);
    }

    /**
     * 求滑动窗口中最小值, 最大值
     * @param a
     * @param m 窗口大小
     */
    public static void first(int[] a, int m) {
        int[] q = new int[100];
        int h = 0, t = -1;
        for (int i = 0; i < a.length; i++) {
            if (h <= t && i - m + 1 > q[h])
                h++;
            while (h <= t && a[q[t]] >= a[i])
                t--;
            q[++t] = i;
            if (i - m + 1 >= 0)
                System.out.println("min: " + a[q[h]]);
        }

        h = 0; t = -1;
        for (int i = 0; i < a.length; i++) {
            if (h <= t && i - m + 1 > q[h]) h++;
            while (h <= t && a[q[t]] <= a[i]) t--;
            q[++t] = i;
            if (i - m + 1 >= 0) System.out.println("max: " + a[q[h]]);
        }
    }

}
